1. Field of the Invention
This invention relates generally to communication systems, and, more particularly, to wireless communication systems.
2. Description of the Related Art
Wireless communication systems include base stations that provide wireless connectivity to associated geographic areas, or cells. Mobile units in a particular cell may access the wireless communication system by establishing a wireless communication link with the base station that serves the cell containing the mobile unit. Among other factors, the size of a cell associated with a base station is limited by the transmission power of mobile units, the sensitivity of the base station to the signals transmitted by the mobile unit, and the transmission power of the base station. For example, the strength of signals received by the mobile unit from the base station is approximately inversely proportional to the square of the distance between the mobile unit and the base station. Accordingly, the radius of the cell served by the base station is approximately proportional to the square root of the transmission power. Furthermore, the maximum data rate that may be used to transmit information from the base station to the mobile unit is inversely related to the range of the base station, i.e., the maximum data transmission rate decreases as the distance between the base station and the mobile unit increases.
Wide-area wireless broadband access is poised to become ubiquitous with the advent of technologies such as WIFI (802.11), WIMAX (802.16) and high data rate cellular systems (UMTS-HSDPA, UMTS-LTE). However, a large number of base stations may be needed to provide coverage to a given area, at least in part because of the inverse relation between the data rate and the base station range, as well as the limitations on range imposed by power discussed above. Backhaul links are used to carry information from each of these base stations back to the network. For example, a backhaul link may be used to connect a base station to a core network, which may be connected to a public network such as an Internet. The backhaul links may be wired and/or wireless.
Although every base station must be connected to the network via a backhaul link, providing a dedicated backhaul link directly from each base station back to a network node may be inefficient. Instead, the wireless communication system may implement mesh or multi-hop networking to improve efficiency. For example, in a distributed wireless communication system that uses base station routers, wireless backhaul links may be used to provide the necessary backhaul solutions. However, the base station router may be relatively far from an access node of the network, but may be relatively close to one or more other base station routers in the network. The base station router may then form a backhaul link to the network via intermediate links to one or more other base station routers, e.g., the wireless backhaul link from the base station router to the network may be formed of a mesh of other base station routers and wireless communication links between these base station routers. Routing in formation from the source to the destination over multiple wireless links of a mesh network has many potential advantages over traditional single-hop networking, such as coverage enhancement, user cooperation diversity, and increased capacity. Mesh networking has therefore been intensively studied in the context of wireless ad-hoc networks.
From a mathematical perspective, the calculation of routes and resources that are allocated in the mesh network can generally be described as an optimization problem that is conventionally referred to as a Simultaneous Routing and Resource Allocation (SRRA) problem. Solutions to the SRRA problem for a particular mesh network should indicate values of one or more network flow variables and communication variables that will maximize a network utility function while meeting given quality of service (QoS) and network constraints. Examples of network variables include data rates per link, injected information per source, and buffer status per node. Examples of communication variables include power per link and codes/spatial/frequency/time resources per link. However, the SRRA problem for a realistic communication network is non-convex and is therefore only local optima can be computed in a reasonable amount of time. The local optima of the non-convex system may correspond to solutions that represent local peaks in the network utility function, but the local optima of a non-convex system are not guaranteed to be global optima of the non-convex system. Consequently, there is no guarantee that the local optima represent a solution that maximizes the network utility function.
At least in part because of the difficulties in solving non-convex problems described above, conventional approaches to routing and resource allocation in mesh networks have attempted to reduce the non-convex problem to a convex problem by adopting various assumptions. For example, the routing and resource allocation problem can be reduced to a convex problem by assuming that each transmission is perfectly orthogonal to every other transmission so that there is no crosstalk interference between transmissions. However, transmissions in realistic wireless communication systems are never perfectly orthogonal and there is always some crosstalk interference between the transmissions. In some cases, the interference, which may be indicated by a signal-to-interference-plus-noise ratio (SINR), can become quite large, which may invalidate the assumption of perfectly orthogonal transmissions and lead to erroneous or irrelevant solutions to the routing and resource allocation problem.
Johansson, et al. (M. Johansson and L. Xiao and S. Boyd, “Simultaneous Routing and Resource Allocation in CDMA Wireless Data Networks”, International Conference on Communication (ICC), Vol. 1 pp. 51-55, Anchorage, Ak., May 2003) discusses one example of a conventional technique for reducing the non-convex routing and resource allocation problem to a convex problem. In the technique described by Johansson, project coordination and the assumption of perfect signal orthogonality are applied to convert the non-convex problem into an equivalent convex one. An approximate capacity formula that is valid for high signal-to-interference plus noise ratios (SINRs) is adopted and the SRRA problem is then solved by standard network flow and power control algorithms that are valid for convex problems. A heuristic link-removal procedure is used to remove links in the network that are not able to meet the assumption of high signal-to-noise ratios and the SRRA problem calculation is repeated with the reduced network topology till all links have high SINR values.
Although the technique described by Johansson converges to a feasible solution, the solution always includes non-zero capacities and power values for all edges in the mesh. Consequently, the solution requires that data be transmitted on all links that are available in the network. Solutions that require transmission on all available links are not optimal and are typically not acceptable in practice. Furthermore, the approximations adopted by Johansson are only valid for high SINRs and this assumption is frequently not met in realistic systems. For example, in CDMA systems, the high SINR assumption can only be met in most cases by applying highly complex interference cancellation techniques. The iterative procedure for removing the links that have low SINR is computational very intensive. For example, a new solution to the convex SRRA problem must be computed after each removal step to find the optimum routing, scheduling and power setting for the reduced network topology. Moreover, the algorithm described by Johansson is heuristic. Heuristic solutions provide no measure of the quality of the solution, which means that the solution provided by the technique described by Johansson is a feasible solution but there is no guarantee that it is an optimal solution.
Fattahi and Pagannini (New Economic Perspectives for Resource Allocation in Wireless Networks”, American Control Conference, pp. 3960-3965, Portland, Oreg., USA, June 2005) apply economic approaches of game theory and bargaining theory to resource allocation in CDMA networks. By applying bargaining theory the SRRA problem can be solved with less complexity even though the problem remains non-convex. Fattahi and Pagannini suggest an iterative algorithm that separates network routing and power allocation and applies bargaining methods to the problem of power allocation. The bargaining methods are implemented in a centralized fashion leading to central power control. The technique described by Fattahi and Pagannini is heuristic and therefore provides no guarantee that the solution is optimal. Furthermore, these approaches are not compatible with standard algorithms and would require completely new hardware and software solutions to implement in current wireless communication systems. Thus, the standard and well-understood power control algorithms implemented in UMTS or CDMA2000 products would have to be abandoned to implement the procedures described by Fattahi and Pagannini.